def car(l):
    "Yeah, so I broke down and wrote car and cdr functions. Leave me alone!"
    return l[0]
def cdr(l):
    """I'm not addicted! errrrr I lie. Maybe I *am* addicted. -_-"""
    return l[1:]
def cadr(l):
    "hah! Don't insult me yet!"
    return l[1]
def fst((x,y)):
    "OK,now that I've implemented caml's fst and snd you are free to insult me"
    return x
def snd((x,y)):
    "and these don't cons either, unlike cdr above!"
    return y
def bifilter(fn, l):
    """fn*[]->([],[]) --Returns the two halves of a list, divided on whether fn returns True or False.

    True half is returned first so as to mimic filter if you want to ignore the second half.
    Same as
    return filter(fn, l), filter(not fn, l)

    >>> #divide everything into odd and even
    >>> bifilter(lambda x: x % 2, [1,2,3,4,5,6])
    ([1, 3, 5], [2, 4, 6])
    >>> #sort some IPs (note that max is used like an n-ary or here ^_^)
    >>> bifilter(lambda s: max([s.startswith(pre) for pre in ['192','127']]), ['192.0.0.255', '127.0.0.1', '172.120.16.201'])
    (['192.0.0.255', '127.0.0.1'], ['172.120.16.201'])
    >>> #sometimes everything might be true (or false), in which you'd probably be better off using filter
    >>> bifilter(lambda x: x < 100, [1,2,3,4,5])
    ([1, 2, 3, 4, 5], [])
    
    This code works properly with iterators, and is likely faster. The
    old code might be a little clearer."""
    t = []; f = []
    for x in l:
        if fn(x): t.append(x)
        else: f.append(x)
    return t,f
#OLD:
#    return filter(fn, l), filter(lambda x:not fn(x), l)
partition = bifilter # a nicer name
def split_step(step, l):
    """int*[]->[[]...]Divides l into step sublists. Each sublist contains every stepth element of l.

    This is equivalent to [l[i::step] for i in range(step)] in Python 2.3
    The old code is maintained to preserve compatibility with Python 2.2
    There are other ways to do this, like:
    [l[i:i+step] for i in range(step)], but this produces different results.
    If you like the other version better, try it out too.
    
    >>> split_step(3,[1,2,3,4,5,6,7])
    [[1, 4, 7], [2, 5], [3, 6]]
    >>> split_step(4,[1,2,3,4,5,6,7])
    [[1, 5], [2, 6], [3, 7], [4]]
    >>> #a real example: extracting the good stuff from a list into separate lists
    >>> #pretend you don't care about the dummy text
    >>> split_step(3, ['dummy', 12, False, 'text', 13, True, 'here', 14, False])
    [['dummy', 'text', 'here'], [12, 13, 14], [False, True, False]]
    """
    return [[l[j] for j in range(i,len(l),step)] for i in range(step)]
def two_time(l):
    """[]->[] -- an list that steps through a list two at a time

    >>> " | ".join(["%s,%s" %(prev,next) for prev,next in two_time([1,2,3,4,5,6])])
    '1,2 | 2,3 | 3,4 | 4,5 | 5,6'
    
    If you want an iterator, (doesn't cons 3*|list|), try using itertools:
        izip(islice(l,0,-1), islice(l,1))
    """
    return zip(l[:-1], l[1:])
def unzip(ts):
    "[[a]]->[[a]]--transpose a matrix made of lists"
    if not ts: return ts # Python 2.3 compatibility: zip() raises TypeError
    return zip(*ts)
transpose = unzip # a much nicer name
def findif(fn, *ls):
    """fn*[]...->any -- Returns first item in l for which fn is true, None if none are.
    If you pass multiple lists, fn must return True given all items

    >>> findif(lambda x:x, ['', '', 'x', 'y'])
    'x'
    >>> findif(lambda x,mask: x > 3 and mask, [1,2,3,4,5], [1,1,0,0,1])
    (5, 1)
    >>> findif(lambda x: x > 13, [1,2,3,4,5])
    >>> #not found, so returns None
    """
    for args in zip(*ls):
        if fn(*args):
            if len(args)==1:
                return car(args)
            else:
                return args
def takewhile(f, l):
    "a->bool*[a]->[a]--requires a list, or something that supports index/slice"
    i = 0
    while i < len(l) and f(l[i]):
        i+=1
    return l[:i]
def takeuntil_inc(fn, l):
    """fn*[]->[]--The inclusive version of takeuntil (which is the inverted version of takewhile)
    (Inclusive, because it includes the element for which it triggered)
    >>> takeuntil_inc(lambda x: x > 2, range(5)) #normal takeuntil would return [0, 1, 2] here
    [0, 1, 2, 3]
    >>> takeuntil_inc(lambda x: x < 2, range(5)) #normal takeuntil would return [] here
    [0]
    """
    for i,x in enumerate(l):
        if fn(x):
            return l[:i+1]
    return l
def every(pred, *ls):
    """fn*[]...->bool -- is pred true for all items in l?

    pred :: any->bool
    >>> all(lambda x: x>5, [7,8,9])
    True
    >>> all(lambda x: x>5, [3,7,8,9])
    False
    >>> all(lambda x: x>5, [])
    True
    """
    for args in zip(*ls):
        if not pred(*args):
            return False
    return True
def some(pred, *ls):
    """fn*[]...->bool -- is pred true for all items in l?

    pred :: any->bool
    >>> any(lambda x: x>5, [3,7,8,9])
    True
    >>> any(lambda x: x>5, [])
    False
    """
    for args in zip(*ls):
        if pred(*args):
            return True
    return False
def same(l):
    """[]->bool | any -- If all elements are equal, return the element, otherwise False

    Notes:
    Returns False for a list of all Falses. Use same_bool if you need to detect a list entirely of False
    Returns False for an empty list.
    Depends on == (__eq__) working properly

    Equivalent to reduce(lambda x,y:x==y and y, l)

    >>> same([1,1,1])
    1
    >>> same([1,0,1])
    False
    >>> same([False,False,False]) #use same_bool to get true
    False
    >>> same([0,0,0]) #same_bool may be wanted here, depending
    0
    """
    if l:
        return reduce(lambda x,y:x==y and x, l)
    else:
        return False
def same_bool(l):
    """[]->bool -- Return whether all elements are equal

    Notes:
    Returns False for an empty list.
    Depends on == (__eq__) working properly

    Equivalent to min([y==l[0] for y in l])

    >>> same_bool([1,1,1])
    True
    >>> same_bool([1,0,1])
    False
    >>> same_bool([False,False,False])
    True
    """
    if l:
        return min([y==l[0] for y in l])
    else:
        return False
def avg(l):
    """[num]->num -- Average a list of numbers.

    Technically this can be anything that implements + and /.
    Mileage may vary for non-numerical objects, however.

    >>> avg([1,2,3,4])
    2.5
    >>> avg([1.0,2.0,3.0,4.0])
    2.5
    """
    if len(l):  return reduce(lambda x,y: x+y, l, 0) / float(len(l))
    else: return 0
def avglists(*lists):
    """[[]...]->[num] -- Averages multiple lists of numbers

    >>> avglists([1,2,3], [4,5,6], [7,8,9])
    [2.0, 5.0, 8.0]
    """
    return map(avg, lists)
def cross(*ls):
    """[[]] -> [[]] Return all permutations of lists in n.

    Examples:
    >>> cross([1],[2,3],[3])
    [[1, 2, 3], [1, 3, 3]]
    >>> cross([1,2,3],[2],[3])
    [[1, 2, 3], [2, 2, 3], [3, 2, 3]]
    """
    if not ls:
        return [[]]
    else:
        rests = cross(*cdr(ls))
        acc = []
        for x in car(ls):
            acc.extend([[x]+rest for rest in rests])
        return acc
def merge(l1,l2):
    """[]*[]->[] -- Return the unique items of both l1 and l2

    >>> merge([1,2,3],[2,3,4])
    [1, 2, 3, 4]
    >>> merge(['N', 'DET', 'ADJ'], ['V', 'N', 'DET'])
    ['N', 'DET', 'ADJ', 'V']

    NOTE:This function is non-destructive. The original documentation made this a bit unclear.
    Also, it relies on __eq__ to do the Right Thing.
    """
    return l1 + filter(lambda x: x not in l1, l2)
def mapn(fn,*ls):
    """fn*[]...->[] -- map a list extending it, not appending
    Can be called with multiple lists

    fn :: value->[values]
    This is different from map's usage, whose fn returns a singleton value for each call.

    >>> mapn(lambda x:[x+1,x+2,x+3], [3,4,5])
    [4, 5, 6, 5, 6, 7, 6, 7, 8]
    >>> mapn(lambda x,y:(x,y), [1,2,3], [4,5,6]) #multiple lists, like a flattening zip
    [1, 4, 2, 5, 3, 6]
    """
    acc = []
    for args in zip(*ls):
        acc.extend(fn(*args))
    return acc
## def starmap_bak(function, iterable):
##     "For 2.2 compatilibity (copied from itertools.py of Python 2.3)"
##     iterable = iter(iterable)
##     while True:
##         yield function(*iterable.next())
## try: #Do we have 2.3's itertools module?
##     import itertools
##     starmap = itertools.starmap
## except ImportError: #if not, use the one of our own invention
##     starmap = starmap_bak
## def enumerate_bak(l):
##     "For 2.2 compatibility"
##     i = 0
##     for x in l:
##         yield i,x
##         i+=1
def filter_dups(l):
    """[] -> [] -- Return a copy of l with all duplicates removed.

    >>> filter_dups([1,2,1])
    [1, 2]
    >>> filter_dups(["DET", "N", "V", "DET", "ADJ", "N"])
    ['DET', 'N', 'V', 'ADJ']

    NOTE:This function is non-destructive. The original documentation made this a bit unclear.
    Also, it relies on __eq__ to do the Right Thing.
    """
    acc=[]
    for x in l:
        if x not in acc:
            acc.append(x)
    return acc
def flatten(l):
    """[]->[] -- Convert all levels of nesting into a single list, consing as needed

    Examples will probably help the most:
    >>> flatten([1,[[2]]])
    [1, 2]
    >>> flatten([[[[[[[1]]]]],[2]],3,4,[[5],6]])
    [1, 2, 3, 4, 5, 6]

    Obviously, this function can be slow*, so be careful!
    *It's highly recursive and creates a new list for each level of recursion.
    """
    flat = []
    for x in l:
        if isinstance(x,list):
            flat += flatten(x)
        else:
            flat.append(x)
    return flat
def concat(ls):
    acc = []
    for l in ls:
        acc += l
    return acc
def tupleise(x):
    """[]->() -- Converts list to tuple recursively

    >>> tupleise([1,[1,2,[3]],4])
    (1, (1, 2, (3,)), 4)
    """
    if isinstance(x,list):
        return tuple([tupleise(y) for y in x])
    else:
        return x
def in_all(x, ls):
    """a'*[]->bool -- Is x in all ls?
    
    >>> in_all(1, ([1],[1],[1]))
    True
    """
    return every(lambda l:x in l, ls)
    ##OLD:
    ##return min([x in l for l in ls]) #one could regard this as a bad pun. but it's a pretty funny one!
def _test():
    import doctest
    doctest.testmod()
if __name__=="__main__":
    _test()
